package 动态规划;

public class Algo494 {
    public static void main(String[] args) {
        int[] nums = {1};
        System.out.println(findTargetSumWays(nums, 2));
    }

    /**
     * 目标和，体会一下回溯算法
     * @param nums
     * @param target
     * @return
     */
    private static int result = 0;


    public static int findTargetSumWays(int[] nums, int target) {
        backTrack(nums, 0, 0, target);
        return result;
    }

    private static void backTrack(int[] nums, int i, int sum, int target) {
        if(i == nums.length-1) {
            if((sum + nums[i]) == target || (sum - nums[i]) == target) {
                result++;
            }
            return;
        }

        sum += nums[i];
        backTrack(nums, i+1, sum, target);
        sum -= nums[i];

        sum -= nums[i];
        backTrack(nums, i+1, sum, target);
    }
}
